<?php
/**
 * <https://y.st./>
 * Copyright © 2018 Alex Yst <mailto:copyright@y.st>
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <https://www.gnu.org./licenses/>.
**/

$xhtml = array(
	'<{title}>' => 'Quick sort',
	'<{subtitle}>' => 'Written in <span title="Data Structures">CS 3303</span> by <a href="https://y.st./">Alexand(er|ra) Yst</a>, finalised on 2018-12-26',
	'<{copyright year}>' => '2018',
	'takedown' => '2017-11-01',
	'<{body}>' => <<<END
<p>
	Below is the code for my submission.
	This is my take on the quick sort algorithm.
	It runs in Θ(n<sup>2</sup>) in the worst case.
	If bad pivot points are chosen every time, the problem doesn&apos;t get properly divided, so the work doesn&apos;t get halved.
	However, in the best case, it runs in Θ(n log<sub>2</sub>n).
	When proper pivot points are chosen, the problem is always split in half, reducing the amount of work each step must complete.
</p>
<p>
	The assignment asks why quick sort is more efficient than insertion sort.
	Insertion sort pays no regard to efficiency, and just gets the job done in a somewhat-intuitive way.
	One of it&apos;s major weaknesses is that it moves several items just to get one item into place.
	It shifts elements down the array, needing to move the item currently in each spot to the next spot down as it does so.
	Quick sort takes a very unintuitive approach.
	It simply moves things around to get the pivot point into the correct spot, ans calls itself recursively on its higher and lower values.
	Above all though, its biggest advantage is that it dosen&apos;t push elements down the array, needing to move several elements out of the way first.
	Quick sort doesn&apos;t always move things directly to where they need to go, and in fact, usually doesn&apos;t.
	However, when it makes a move, even a temporary one, it performs a direct swap.
	It only swaps two items, and not half the items in the array or more.
	Insertion swap isn&apos;t afraid to move literally every item in the array on the first step, at times.
</p>
<p>
	The assignment specifically tells us to provide a measure of efficiency in the form of the number of swaps the algorithm must perform.
	I think this metric, when taken alone, can be a bit misleading.
	However, we can very much optimise for it.
	My version of the quick sort, for that reason, does not perform swaps that move items away from the partition they need to be in for the given recursion level.
	Some unnecessary moves are still performed, however, checks are performed to drastically reduce their number.
	For the provided list of integers, I got my swap count to <code>22</code>.
	I didn&apos;t know what to think of this number at first.
	It lacked context; I couldn&apos;t say I was surprised, but I also didn&apos;t know how efficient that was supposed to be.
	So I started trying to visualise the perfect number of swaps needed to sort the array, if it was perfectly disordered.
	Assuming you swapped items only as many times as absolutely necessary, you&apos;d need n-1 direct swaps, where n is the number of items in the array (or if the array isn&apos;t perfectly disordered, n would be the number of items out of place).
	The array we&apos;re working with in this assignment is <code>21</code> items long, so my sorting algorithm only performs <code>2</code> unnecessary swaps.
	Given the context, I&apos;d say that&apos;s rather good!
	We could reach the perfect number of swaps by searching the array for the smallest number, swapping it into place, then searching the remaining array for the smallest number, and so on.
	But that adds a lot of overhead.
	Given the low overhead of quick sort, I find it very surprising that the swap count could be brought that close to the theoretical minimum.
	However, as I mentioned before, looking at the number of swaps can be misleading.
	In order to get my swap count, I upped the number of comparisons made so items would not swapped away from the sub-array they belong in, which in turn added overhead as well.
</p>
<p>
	Given the list of integers we were assigned to feed out sorting algorithm, the output of my version of the algorithm is as follows:
</p>
<blockquote>
<pre><code>Number of swaps performed: 22
Sorted array: [0, 1, 2, 3, 4, 9, 10, 12, 14, 23, 29, 31, 45, 69, 75, 77, 88, 91, 99, 101, 120]</code></pre>
</blockquote>
<p>
	Without further ado, the code:
</p>
<blockquote>
<pre><code>/**
 * CS 3303 Unit 5 quick sort assignment submission
 * Copyright © 2018 Alex Yst &lt;mailto:copyright@y.st&gt;
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see &lt;https://www.gnu.org./licenses/&gt;.
**/

public class Unit6 {
	public static int count = 0;
	public static int[] array = {12,9,4,99,120,1,3,10,23,45,75,69,31,88,101,14,29,91,2,0,77};
	public static void main(String[] args) {
		QuickSort(0, 20);
		System.out.println(&quot;Number of swaps performed: &quot; + count);
		System.out.println(&quot;Sorted array: &quot; + java.util.Arrays.toString(array));
	}
	public static void QuickSort(int begin, int end) {
		if(begin &lt; end) {
			int bottom_unsorted = begin;
			int top_unsorted = end;
// Integer division; this&apos;ll always result in an integer, not a float.
			int pivot = (bottom_unsorted + top_unsorted) / 2;
// There&apos;s no need to touch values that are already in the correct sub-array.
			while(array[bottom_unsorted] &lt; array[pivot]) {
				bottom_unsorted++;
			}
			while(array[top_unsorted] &gt; array[pivot]) {
				top_unsorted--;
			}
// The current index must *never* be the pivot point.
			int current;
			if(top_unsorted != pivot) {
				current = top_unsorted;
			} else {
				current = bottom_unsorted;
			}
			while(bottom_unsorted != pivot || top_unsorted != pivot) {
				int swap;
				if(array[current] &lt; array[pivot]) {
					swap = bottom_unsorted;
					bottom_unsorted++;
				} else {
				   swap = top_unsorted;
				   top_unsorted--;
				}
				int temp = array[swap];
				array[swap] = array[current];
				array[current] = temp;
				count++;
				if(swap == pivot) {
					pivot = current;
				}
// There&apos;s no need to move values that are already in the correct sub-array.
				while(array[bottom_unsorted] &lt; array[pivot]) {
					bottom_unsorted++;
				}
				while(array[top_unsorted] &gt; array[pivot]) {
					top_unsorted--;
				}
// The current index must *never* be the pivot point.
				if(top_unsorted != pivot) {
					current = top_unsorted;
				} else {
					current = bottom_unsorted;
				}
			} // endwhile
			QuickSort(begin, pivot - 1);
			QuickSort(pivot + 1, end);
		} // endif
	}
}</code></pre>
</blockquote>
END
);
